查看原文
其他

双链表的操作示例(附代码)

ZhengN 嵌入式大杂烩 2021-01-31

什么是双链表?

双链表是在操作系统中常用的数据结构,它的每个数据结点中都有两个指针,分别指向直接后继和直接前驱,其结点组成如下:


其示意图举例如下:

双链表的操作示例

1、双链表结点定义:

/* 数据元素类型 */
typedef int Type;

/* 双链表结点结构体 */
typedef struct _DListNode
{

struct _DListNode * prior; /* 指向直接前趋结点 */
struct _DListNode * next; /* 指向直接后继结点 */
Type data; /* 数据 */
}DListNode;

2、相关操作示例

/* 函数声明 */
static DListNode *dlist_create(void);
static int dlist_find(DListNode *dlist, Type find_data);
static DListNode *dlist_change(DListNode *dlist, int pos, Type new_data);
static DListNode *dlist_insert(DListNode *dlist, Type insert_data, int pos);
static DListNode *dlist_delete(DListNode *dlist, Type del_data);
static void dlist_print_int(DListNode *dlist);

(1)创建一个双链表:(5,2,0,13,14)

示意图:

代码:

static DListNode *dlist_create(void)
{
/* 创建第一个结点 */
DListNode *node = (DListNode*)malloc(sizeof(DListNode));
node->prior = NULL;
node->next = NULL;
node->data = list[0];

/* 创建头指针并指向第一个结点 */
DListNode *head = node;

/* 创建其它结点并链接成双链表 */
for (int i = 1; i < LEN; i++)
{
/* 创建新结点 */
DListNode *new_node = (DListNode*)malloc(sizeof(DListNode));
new_node->next = NULL;
new_node->prior = head; /* 关键点1:新结点的prior指针指向前驱结点 */
new_node->data = list[i];

/* 改变前驱结点的next指针指向 */
head->next = new_node; /* 关键点2:前驱结点的next指针指向新结点 */

/* 头指针后移 */
head = head->next;
}

return node;
}

(2)元素查找:

static int dlist_find(DListNode *dlist, Type find_data)
{
DListNode* temp = dlist;
int pos = 1;

while (temp)
{
if (find_data == temp->data)
{
return pos;
}
else
{
temp = temp->next;
pos++;
}
}

return ERROR;
}

(3)元素替换:

static DListNode *dlist_change(DListNode *dlist, int pos, Type new_data)
{
DListNode* temp = dlist;

for (int i = 1; i < pos; i++)
{
temp = temp->next;
}
temp->data = new_data;

return dlist;
}

(4)结点插入:

  • 头部插入:

  • 中间插入:

  • 尾部插入:

static DListNode *dlist_insert(DListNode *dlist, Type insert_data, int pos)
{
/* 创建新结点待插入 */
DListNode *new_node = (DListNode*)malloc(sizeof(DListNode));
new_node->next = NULL;
new_node->prior = NULL;
new_node->data = insert_data;

if (pos > LEN + 1)
{
printf("插入的位置错误!\n");
}

/* 头部插入 */
if (1 == pos)
{
dlist->prior = new_node; /* 步骤1 */
new_node->next = dlist; /* 步骤2 */
dlist = new_node; /* 步骤3 */
}
else
{
DListNode *temp = dlist;
for (int i = 1; i < pos-1; i++)
{
temp = temp->next;
}
/* 中间插入 */
if (temp->next != NULL)
{
new_node->next = temp->next; /* 步骤1 */
new_node->prior = temp; /* 步骤2 */
temp->next->prior = new_node; /* 步骤3 */
temp->next = new_node; /* 步骤4 */
}
/* 尾部插入 */
else
{
temp->next = new_node; /* 步骤1 */
new_node->prior = temp; /* 步骤2 */
}
}

return dlist;
}

(5)结点删除:

static DListNode *dlist_delete(DListNode *dlist, Type del_data)
{
DListNode *temp = dlist;

while (temp)
{
if (del_data == temp->data)
{
temp->next->prior = temp->prior;
temp->prior->next = temp->next;
free(temp);
return dlist;
}
temp = temp->next;
}

return dlist;
}

3、验证

主函数:

int main(void)
{
printf("创建一个双链表:");
DListNode *dlist = dlist_create();
dlist_print_int(dlist);

printf("元素13所在的位置是:");
int pos = dlist_find(dlist, 13);
if (ERROR == pos)
{
printf("该元素不存在。\n");
}
else
{
printf("%d\n", pos);
}

printf("把第1个位置的元素替换为2020得到新的双链表为:");
dlist = dlist_change(dlist, 1, 2020);
dlist_print_int(dlist);

printf("第2个位置插入888得到新的双链表为:");
dlist = dlist_insert(dlist, 888, 2);
dlist_print_int(dlist);

printf("删除元素2得到新的双链表为:");
dlist = dlist_delete(dlist, 2);
dlist_print_int(dlist);

return 0;
}

运行结果:

最后

以上就是本次分享的双链表的笔记,希望各位喜欢!如有错误欢迎指出。以上代码仅用于学习使用,可能没有那么完善、严谨,还望谅解。

最后,如果可以的话,麻烦帮忙分享、转发、再看,谢谢。

完整代码贴出来太长了影响阅读,有需要的朋友可在后台回复:双链表,即可获取链接。若链接失效,可添加我的微信:li1459193463。


猜你喜欢:

ARM Cortex-M 系列 MCU错误代码自动追踪库的使用

C语言、嵌入式位操作精华技巧大汇总

遇到指针别害怕!先把这篇笔记看一遍~

【数据结构笔记】单链表

【数据结构笔记】头插法与尾插法创建单链表

C语言,环形队列



    您可能也对以下帖子感兴趣

    文章有问题?点此查看未经处理的缓存